package org.hot100.h046;

import java.util.*;

/**
 * @Author: wjy
 * @Date: 2021/12/20 11:05
 */
public class Solution {

    /**
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     *
     * 示例 1：
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     *
     * 示例 2：
     * 输入：nums = [0,1]
     * 输出：[[0,1],[1,0]]
     *
     * 示例 3：
     * 输入：nums = [1]
     * 输出：[[1]]
     *
     * @param args
     */
    public static void main(String[] args) {

        int[] ints = {1, 2, 3};

        Solution solution = new Solution();
        System.out.println(solution.permute(ints));

    }

    List<List<Integer>> res = new LinkedList<>();
    int[] temps;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        this.temps = nums;
        this.recursive4(0);
        System.out.println(res);
        return res;
    }

    public List<List<Integer>> permute2(int[] nums) {
        temps = nums;
        recursive2(0);
        return res;
    }

/*    public void recursive(int m) {
        if (m == temps.length - 1) {
            Integer[] integers = new Integer[temps.length];
            for (int i = 0; i < temps.length; i++) {
                integers[i] = temps[i];
            }
            res.add(new LinkedList<>(Arrays.asList(integers)));
        }
        HashSet<Integer> set = new HashSet<>();
        for (int i = m; i < temps.length; i++) {
            if (set.contains(temps[i])) {
                continue;
            }
            set.add(temps[i]);
            this.swap(i, m);
            this.recursive(m + 1);
            this.swap(i, m);
        }

    }*/

    public void recursive(int m) {
        if (m == temps.length - 1) {
            Integer[] integers = new Integer[temps.length];
            for (int i = 0; i < temps.length; i++) {
                integers[i] = temps[i];
            }

            List<Integer> list = new LinkedList<>(Arrays.asList(integers));
            res.add(list);
        } else {
            HashSet<Integer> set = new HashSet<>();
            for (int i = m; i < temps.length; i++) {
                if (set.contains(temps[i])) {
                    continue;
                }
                set.add(temps[i]);
                swap(i, m);
                recursive(m + 1);
                swap(i, m);
            }
        }

    }

    public void recursive2(int m) {
        if (m == temps.length - 1) {
            Integer[] integers = new Integer[temps.length];
            for (int i = 0; i < integers.length; i++) {
                integers[i] = temps[i];
            }
            res.add(new LinkedList<>(Arrays.asList(integers)));
        } else {
            for (int i = m; i < temps.length; i++) {
                swap(i, m);
                recursive2(m + 1);
                swap(i, m);
            }
        }
    }

    public void recursive3(int m) {
        if (m == temps.length - 1) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < temps.length; i++) {
                list.add(temps[i]);
            }
            res.add(list);
        } else {
            for (int i = m; i < temps.length; i++) {
                swap(m, i);
                recursive3(m + 1);
                swap(m, i);
            }
        }
    }

    public void recursive4(int m) {
        if (m == temps.length - 1) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < temps.length; i++) {
                list.add(temps[i]);
            }
            res.add(list);
        } else {
            for (int i = m; i < temps.length; i++) {
                swap(i, m);
                recursive4(m + 1);
                swap(i, m);
            }
        }
    }

    public void swap(int a, int b) {
        int c = temps[a];
        temps[a] = temps[b];
        temps[b] = c;
    }

}
